package com.leecode.xiehf.page_02;

import com.leecode.Printer;

/**
 * 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
 * <p>
 *"ADOBECODEBANC"
 * "ABC"
 *     "abcabdebac"
 * "cda"
 * 注意：如果 s 中存在这样的子串，我们保证它是唯一的答案。
 * https://leetcode-cn.com/problems/minimum-window-substring/
 */
public class Solution_0076 extends Printer {

    public static void main(String[] args) {
        Solution_0076 solution = new Solution_0076();
//        String s = solution.minWindow("caacbabbbcacbabaabcbbbcbbcbbbbbbabbcacbbcbabccbabbc", "bababbcabccccbabbacacb");
        String s = solution.minWindow("ADOBECODEBANC", "ABC");
        print(s);
    }

    public String minWindow(String s, String t) {
        int sLen = s.length();
        int tLen = t.length();
        if (sLen == 0 || tLen == 0) {
            return "";
        }
        int[] tFreq = new int[128];
        for (int i = 0; i < tLen; i++) {
            int c = t.charAt(i);
            tFreq[c]++;
        }
        int[] winFreq = new int[128];
        int left = 0, right = 0, distance = 0, begin = 0;
        int minLen = sLen + 1;
        // [left, right)
        while (right < sLen) {
            int r = s.charAt(right);
            if (tFreq[r] == 0) {
                right++;
                continue;
            }
            if (winFreq[r] < tFreq[r]) {
                distance++;
            }
            winFreq[r]++;
            right++;
            while (distance == tLen) {
                if (right - left < minLen) {
                    minLen = right - left;
                    begin = left;
                }
                int l = s.charAt(left);
                if (tFreq[l] == 0) {
                    left++;
                    continue;
                }
                if (winFreq[l] == tFreq[l]) {
                    distance--;
                }
                winFreq[l]--;
                left++;
            }
        }
        if (minLen == sLen + 1) {
            return "";
        }
        return s.substring(begin, begin + minLen);
    }


    public String minWindow1(String s, String t) {
        int length = s.length();
        if (length == 0 || t.length() == 0) {
            return "";
        }
        String res = "";
        int len = 0;
        char[] chars = t.toCharArray();
        for (int i = 0; i <= length - t.length(); i++) {
            int c = t.indexOf(s.charAt(i));
            if (c >= 0) {
                swap(chars, 0, c);
                int end = minWindow(s, i, chars, 1);
                swap(chars, 0, c);
                if (end > i) {
                    System.out.println(end - i);
                    if (len == 0) {
                        len = end - i;
                        res = s.substring(i, end);
                    } else {
                        if (end - i < len) {
                            len = end - i;
                            res = s.substring(i, end);
                        }
                    }
                }
            }
        }
        return res;
    }

    private int minWindow(String s, int i, char[] chars, int num) {
        if (num == chars.length) {
            return i + 1;
        }
        for (int j = i + 1; j < s.length() - chars.length + num + 1; j++) {
            char c = s.charAt(j);
            int idx = indexOf(chars, num, c);
            if (idx > 0) {
                swap(chars, idx, num);
                int end = minWindow(s, j, chars, num+1);
                swap(chars, idx, num);
                if (end > j) {
                    return end;
                }
            }
        }
        return i;
    }

    private int indexOf(char[] chars, int fromIndex, char c) {
        for (int i = fromIndex; i < chars.length; i++) {
            if (chars[i] == c) {
                return i;
            }
        }
        return -1;
    }

    private void swap(char[] chars, int left, int right) {
        if (right == chars.length) {
            return;
        }
        if (left == right) {
            return;
        }
        char tmp = chars[left];
        chars[left] = chars[right];
        chars[right] = tmp;
    }
}
